{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #01 Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: updateMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #01 矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 <code>0</code> 和 <code>1</code> 组成的矩阵 <code>mat</code> ，请输出一个大小相同的矩阵，其中每一个格子是 <code>mat</code> 中对应位置元素到最近的 <code>0</code> 的距离。</p>\n",
    "\n",
    "<p>两个相邻元素间的距离为 <code>1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626667201-NCWmuP-image.png\" style=\"width: 150px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat =<strong> </strong>[[0,0,0],[0,1,0],[0,0,0]]\n",
    "<strong>输出：</strong>[[0,0,0],[0,1,0],[0,0,0]]\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626667205-xFxIeK-image.png\" style=\"width: 150px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>mat =<b> </b>[[0,0,0],[0,1,0],[1,1,1]]\n",
    "<strong>输出：</strong>[[0,0,0],[0,1,0],[1,2,1]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= m * n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>mat[i][j] is either 0 or 1.</code></li>\n",
    "\t<li><code>mat</code> 中至少有一个 <code>0 </code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [01-matrix](https://leetcode.cn/problems/01-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [01-matrix](https://leetcode.cn/problems/01-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0],[0,1,0],[0,0,0]]', '[[0,0,0],[0,1,0],[1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dist = [[sys.maxsize] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "                else:\n",
    "                    if i-1 >= 0:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i-1][j]+1)\n",
    "                    if j-1 >= 0:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i][j-1]+1)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if mat[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "                else:\n",
    "                    if i+1 < m:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i+1][j]+1)\n",
    "                    if j+1 < n:\n",
    "                        dist[i][j] = min(dist[i][j], dist[i][j+1]+1)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        \n",
    "        di=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        tem=[]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    tem.append((i,j))\n",
    "                else:\n",
    "                    matrix[i][j]=-1\n",
    "        step=1\n",
    "        while tem:\n",
    "            l=len(tem)\n",
    "            for i in range(l):\n",
    "                n=tem.pop(0)\n",
    "                for d in di:\n",
    "                    x=n[0]+d[0]\n",
    "                    y=n[1]+d[1]\n",
    "                    if x>=0 and x<len(matrix) and y>=0 and y<len(matrix[0]):\n",
    "                        if matrix[x][y]<0:\n",
    "                            matrix[x][y]=step\n",
    "                            tem.append((x,y))\n",
    "            step+=1\n",
    "        return matrix\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class ArrayQueue:\n",
    "    DEFAULT_CAPACITY=10\n",
    "    def __init__(self):\n",
    "        self._data=[(None,)]*ArrayQueue.DEFAULT_CAPACITY\n",
    "        self._size=0\n",
    "        self._front=0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self._size==0\n",
    "\n",
    "    def first(self):\n",
    "        if self.isEmpty():\n",
    "            return '队列为空'\n",
    "        return self._data[self._front]\n",
    "\n",
    "    def dequeue(self):\n",
    "        if self.isEmpty():\n",
    "            return '队列为空'\n",
    "        result=self._data[self._front]\n",
    "        self._data[self._front]=None\n",
    "        self._front=(self._front+1)%len(self._data)\n",
    "        self._size-=1\n",
    "        if 0<self._size<len(self._data)//4:\n",
    "            self._resize(len(self._data)//2)\n",
    "\n",
    "        return result\n",
    "\n",
    "    def _resize(self,cap):\n",
    "        old=self._data\n",
    "        self._data=[None]*cap\n",
    "        walk=self._front\n",
    "        for k in range(self._size):\n",
    "            self._data[k]=old[walk]\n",
    "            walk=(1+walk)%len(old)\n",
    "        self._front=0\n",
    "\n",
    "    def enqueue(self,e):\n",
    "        if self._size==len(self._data):\n",
    "            self._resize(2*len(self._data))\n",
    "\n",
    "        location=(self._front+self._size)%len(self._data)\n",
    "        self._data[location]=e\n",
    "        self._size+=1\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self,matrix,row,col):\n",
    "        while not self.queue.isEmpty():\n",
    "            loca_x,loca_y=self.queue.dequeue()\n",
    "            if loca_x-1>=0:\n",
    "                neighbor=matrix[loca_x-1][loca_y]\n",
    "                now=matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor>now+1:\n",
    "                    matrix[loca_x-1][loca_y]=now+1\n",
    "                    self.queue.enqueue((loca_x-1,loca_y))\n",
    "\n",
    "            if loca_x+1<row:\n",
    "                neighbor = matrix[loca_x + 1][loca_y]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x + 1][loca_y] = now + 1\n",
    "                    self.queue.enqueue((loca_x+1,loca_y))\n",
    "\n",
    "            if loca_y-1>=0:\n",
    "                neighbor = matrix[loca_x][loca_y-1]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x][loca_y-1] = now + 1\n",
    "                    self.queue.enqueue((loca_x,loca_y-1))\n",
    "\n",
    "            if loca_y+1<col:\n",
    "                neighbor = matrix[loca_x][loca_y + 1]\n",
    "                now = matrix[loca_x][loca_y]\n",
    "\n",
    "                if neighbor > now+1:\n",
    "                    matrix[loca_x][loca_y + 1] = now + 1\n",
    "                    self.queue.enqueue((loca_x,loca_y+1))\n",
    "\n",
    "\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        row=len(matrix)\n",
    "        col=len(matrix[0])\n",
    "        self.queue=ArrayQueue()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if matrix[i][j]==0:\n",
    "                    self.queue.enqueue((i,j))\n",
    "                else:\n",
    "                    matrix[i][j]=math.inf\n",
    "\n",
    "\n",
    "        self.bfs(matrix,row,col)\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        directs = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                else:\n",
    "                    matrix[i][j] = sys.maxsize\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dx, dy in directs:\n",
    "                tx, ty = x + dx, y + dy\n",
    "                if 0 <= tx < m and 0 <= ty < n and matrix[tx][ty] > matrix[x][y] + 1:\n",
    "                    queue.append((tx, ty))\n",
    "                    matrix[tx][ty] = matrix[x][y] + 1\n",
    "\n",
    "        return matrix\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        \n",
    "        for i in range(0, row):\n",
    "            for j in range(0, col):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] = row + col\n",
    "                if i > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)\n",
    "                if j > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)\n",
    "        for i in range(row-1, -1, -1):\n",
    "            for j in range(col-1, -1, -1):\n",
    "                if i < row - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)\n",
    "                if j < col - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if matrix == []:\n",
    "            return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[float('inf')] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)\n",
    "                    if j > 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)\n",
    "                        \n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i < m - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)\n",
    "                    if j < n - 1:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)\n",
    "        return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        Q = []\n",
    "        visited = set()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    Q.append((i, j))\n",
    "                    visited.add((i, j))\n",
    "        \n",
    "        while Q:\n",
    "            i, j = Q.pop(0)\n",
    "            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:\n",
    "                    matrix[x][y] = matrix[i][j] + 1\n",
    "                    visited.add((x, y))\n",
    "                    Q.append((x, y))\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: 'List[List[int]]') -> 'List[List[int]]':\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return []\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return []\n",
    "\n",
    "        def BFS(matrix, i, j):\n",
    "            distance = 0\n",
    "            visit, queue = {(i, j)}, deque([(i, j)])\n",
    "            while queue:\n",
    "                size = len(queue)\n",
    "                for _ in range(size):\n",
    "                    x, y = queue.popleft()\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        if matrix[x][y] == 0:\n",
    "                            ans[i][j] = distance\n",
    "                            return\n",
    "                        visit.add((x, y))\n",
    "                        queue.extend([\n",
    "                            (x - 1, y), (x + 1, y),\n",
    "                            (x, y - 1), (x, y + 1)\n",
    "                        ])\n",
    "                distance += 1\n",
    "\n",
    "        ans = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                BFS(matrix, i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        Q = collections.deque([])\n",
    "        visited = set()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    Q.append((i,j))\n",
    "                    visited.add((i,j))\n",
    "        while Q :\n",
    "            i,j = Q.popleft()\n",
    "            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:\n",
    "                if 0 <= x < m and 0<= y <n and (x,y) not in visited:\n",
    "                    matrix[x][y] = matrix[i][j] + 1\n",
    "                    visited.add((x,y))\n",
    "                    Q.append((x,y))\n",
    "        return matrix\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return matrix\n",
    "        \n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        \n",
    "        area=m*n\n",
    "        \n",
    "        dp=[[0 for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                else:\n",
    "                    up,left=area,area\n",
    "                    if i>0:\n",
    "                        up=dp[i-1][j]\n",
    "                    if j>0:\n",
    "                        left=dp[i][j-1]\n",
    "                    dp[i][j]=min(up+1,left+1)\n",
    "                    \n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]=0\n",
    "                else:\n",
    "                    down,right=area,area\n",
    "                    if i<m-1:\n",
    "                        down=dp[i+1][j]\n",
    "                    if j<n-1:\n",
    "                        right=dp[i][j+1]\n",
    "                    dp[i][j]=min(down+1,right+1,dp[i][j])\n",
    "                    \n",
    "        return dp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        # if len(matrix) == 0:return []\n",
    "        refresh = []\n",
    "        c = 0\n",
    "        l = len(matrix)\n",
    "        h = len(matrix[0])\n",
    "\n",
    "        res = [[10000 for i in range(h)] for j in range(l)]\n",
    "        for k, i in enumerate(matrix):\n",
    "            for kk, j in enumerate(i):\n",
    "                if j == 0:\n",
    "                    c += 1\n",
    "                    refresh.append([k, kk])\n",
    "                    res[k][kk]=0\n",
    "\n",
    "        while c < h * l:\n",
    "            now = refresh.pop(0)\n",
    "            k = now[0]\n",
    "            kk = now[1]\n",
    "            re = res[k][kk] + 1\n",
    "            if k > 0 and res[k - 1][kk]>re:\n",
    "                res[k - 1][kk] = re\n",
    "                refresh.append([k-1, kk])\n",
    "                c += 1\n",
    "            if k < l - 1 and res[k + 1][kk]> re:\n",
    "                res[k + 1][kk] = re\n",
    "                c += 1\n",
    "                refresh.append([k+1, kk])\n",
    "            if kk > 0 and  res[k][kk - 1]> re:\n",
    "                res[k][kk - 1] = re\n",
    "                c += 1\n",
    "                refresh.append([k, kk-1])\n",
    "            if kk < h - 1 and res[k][kk + 1]> re:\n",
    "                res[k][kk + 1] = re\n",
    "                c += 1\n",
    "                refresh.append([k, kk+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        result = [[10000 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    result[i][j] = 0\n",
    "        num = 0\n",
    "        flag = 1\n",
    "        while flag:\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if result[i][j] == num:\n",
    "                        if i > 0:\n",
    "                            result[i - 1][j] = min(num + 1, result[i - 1][j])\n",
    "                        if i < m - 1:\n",
    "                            result[i + 1][j] = min(num + 1, result[i + 1][j])\n",
    "                        if j > 0:\n",
    "                            result[i][j - 1] = min(num + 1, result[i][j - 1])\n",
    "                        if j < n - 1:\n",
    "                            result[i][j + 1] = min(num + 1, result[i][j + 1])\n",
    "                    if result[i][j] == 10000:\n",
    "                        flag = 1\n",
    "            num += 1\n",
    "        return result\n",
    "                            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        rows = len(matrix)\n",
    "        if rows == 0:\n",
    "            return []\n",
    "        cols = len(matrix[0])\n",
    "        if cols == 0:\n",
    "            return [[]]\n",
    "        ret = [[100000] * cols for _ in range(rows)]\n",
    "        v = [[False] * cols for _ in range(rows)]\n",
    "        q = []\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if matrix[r][c] == 0:\n",
    "                    q.append((r, c))\n",
    "                    v[r][c] = True\n",
    "                    ret[r][c] = 0\n",
    "        det = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        while len(q) > 0:\n",
    "            new_q = []\n",
    "            for i in q:\n",
    "                r, c = i\n",
    "                for dr, dc in det:\n",
    "                    if (0 <= r + dr < rows) and (0 <= c + dc < cols) and not v[r + dr][c + dc]:\n",
    "                        v[r + dr][c + dc] = True\n",
    "                        ret[r + dr][c + dc] = min(ret[r + dr][c + dc], ret[r][c] + 1)\n",
    "                        new_q.append((r + dr, c + dc))\n",
    "            q = new_q\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/01-matrix/description/\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class Node(object):\n",
    "    position = None\n",
    "    weight = None\n",
    "\n",
    "    def __init__(self, position, weight):\n",
    "        self.position = position\n",
    "        self.weight = weight\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.weight < other.weight\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.weight == other.weight\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        if not matrix or not matrix[0]:\n",
    "            return matrix\n",
    "\n",
    "        marked = set()\n",
    "        pQueue = PriorityQueue()\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, val in enumerate(row):\n",
    "                if val == 0:\n",
    "                    pQueue.put(Node((i, j), 0))\n",
    "                else:\n",
    "                    matrix[i][j] = float('+inf')\n",
    "\n",
    "        while not pQueue.empty():\n",
    "            node = pQueue.get()\n",
    "            position = node.position\n",
    "            if position in marked:\n",
    "                continue\n",
    "            marked.add(position)\n",
    "\n",
    "            weight = node.weight\n",
    "            positions = [(position[0] - 1, position[1]),\n",
    "                         (position[0] + 1, position[1]),\n",
    "                         (position[0], position[1] - 1),\n",
    "                         (position[0], position[1] + 1)]\n",
    "            positions = [position for position in positions if 0 <= position[0] < m and 0 <= position[1] < n]\n",
    "\n",
    "            for p in positions:\n",
    "                if p in marked:\n",
    "                    continue\n",
    "\n",
    "                if weight + 1 < matrix[p[0]][p[1]]:\n",
    "                    matrix[p[0]][p[1]] = weight + 1\n",
    "                pQueue.put(Node(p, matrix[p[0]][p[1]]))\n",
    "\n",
    "        return matrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                l,t= 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = matrix[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = matrix[i][j - 1]\n",
    "                    \n",
    "                    matrix[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(matrix) - 1, -1 ,-1):\n",
    "            for j in range(len(matrix[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i < len(matrix) - 1:\n",
    "                        b = matrix[i + 1][j]\n",
    "\n",
    "                    if j < len(matrix[0]) - 1:\n",
    "                        r = matrix[i][j + 1]\n",
    "\n",
    "                    matrix[i][j] = min(matrix[i][j], min(r,b) + 1)\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                up = 100000\n",
    "                left = 100000\n",
    "                if matrix[i][j]!= 0 :\n",
    "                    if i>0:\n",
    "                        up = matrix[i-1][j]\n",
    "                    if j>0:\n",
    "                        left = matrix[i][j-1]\n",
    "                    matrix[i][j] = min(up,left) +1\n",
    "        \n",
    "        for i in range(len(matrix)-1,-1,-1):\n",
    "            for j in range(len(matrix[0])-1,-1,-1):\n",
    "                down = 100000\n",
    "                right = 100000\n",
    "                if matrix[i][j]!= 0 :\n",
    "                    if i<len(matrix)-1:\n",
    "                        down = matrix[i+1][j]\n",
    "                    if j<len(matrix[0])-1:\n",
    "                        right = matrix[i][j+1]\n",
    "                    matrix[i][j] =min(matrix[i][j], min(down,right) +1)    \n",
    "        return matrix        \n",
    "        # import numpy\n",
    "        # from collections import deque\n",
    "        # dis = numpy.zeros((len(matrix),len(matrix[0])),dtype = numpy.int)\n",
    "        # for i in range(len(matrix)):\n",
    "        #     for j in range(len(matrix[0])):\n",
    "        #         queue = deque([[i,j]])\n",
    "        #         step = 0\n",
    "        #         if matrix[i][j] == 0:\n",
    "        #             dis[i][j] = 0\n",
    "        #         else:   \n",
    "        #             flage = False\n",
    "        #             while(queue and not flage):\n",
    "        #                 l = len(queue)\n",
    "        #                 step +=1\n",
    "        #                 for _ in range(l):\n",
    "        #                     cur = queue.pop()\n",
    "        #                     if cur[0] > 0 :\n",
    "        #                         cur_next = [cur[0]-1,cur[1]]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]] == 0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        #                     if cur[0] < len(matrix)-1:\n",
    "        #                         cur_next = [cur[0]+1,cur[1]]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]]==0:\n",
    "        #                             dis[i,j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        #                     if cur[1] > 0:\n",
    "        #                         cur_next = [cur[0],cur[1]-1]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]]==0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "\n",
    "        #                     if cur[1] < len(matrix[0])-1:\n",
    "        #                         cur_next = [cur[0],cur[1]+1]\n",
    "        #                         if matrix[cur_next[0]][cur_next[1]] == 0:\n",
    "        #                             dis[i][j] = step\n",
    "        #                             flage = True\n",
    "        #                             break\n",
    "        #                         else:\n",
    "        #                             queue.appendleft(cur_next)\n",
    "        # return dis.tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        dirct=[[0,-1],[1,0],[0,1],[-1,0]]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    num=0\n",
    "                    q=[[i,j,num]]\n",
    "                    while q:\n",
    "                        c=q.pop(0)\n",
    "                        num =c[2]+ 1\n",
    "                        for o in dirct:\n",
    "                            if 0<=o[0]+c[0]<=len(matrix)-1 and 0<=o[1]+c[1]<=len(matrix[0])-1:\n",
    "                               q.append([o[0]+c[0],o[1]+c[1],num])\n",
    "                        if matrix[c[0]][c[1]] == 0:\n",
    "                            matrix[i][j]=c[2]\n",
    "                            break\n",
    "        return matrix\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        directions=[(-1,0),(1,0),(0,1),(0,-1)]\n",
    "        \n",
    "        res=matrix\n",
    "\n",
    "        def Is(x,y):\n",
    "            return x>=0 and x<m and y>=0 and y<n\n",
    "\n",
    "        def bfs(x,y):\n",
    "            queue=deque([(x,y,0)])\n",
    "            visited=set([(x,y)])\n",
    "            while queue:\n",
    "                i,j,dis=queue.popleft()\n",
    "                for direction in directions:\n",
    "                    new_i,new_j=i+direction[0],j+direction[1]\n",
    "                    if Is(new_i,new_j) and (new_i,new_j) not in visited:\n",
    "                        visited.add((new_i,new_j))\n",
    "                        if matrix[new_i][new_j]==0:\n",
    "                            return dis+1\n",
    "                        queue.append((new_i,new_j,dis+1))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if res[i][j]==1:\n",
    "                    res[i][j]=bfs(i,j)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        dij = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        ra = len(matrix)\n",
    "        co = len(matrix[0])\n",
    "        que = []\n",
    "        \n",
    "        for i in range(ra):\n",
    "            for j in range(co):\n",
    "                if matrix[i][j]:\n",
    "                    mi = min(matrix[ni][nj] for ni,nj in filter(lambda x: -1<x[0]<ra and -1<x[1]<co, ((i+di,j+dj) for di, dj in dij)))\n",
    "                    if matrix[i][j] == mi:\n",
    "                        que.append((i, j))\n",
    "        while que:\n",
    "            tmp = []\n",
    "            for i,j in que:\n",
    "                matrix[i][j] += 1\n",
    "                \n",
    "            for i,j in que:\n",
    "                mi = min(matrix[ni][nj] for ni,nj in filter(lambda x: -1<x[0]<ra and -1<x[1]<co, ((i+di,j+dj) for di, dj in dij)))\n",
    "                if matrix[i][j] == mi:\n",
    "                    tmp.append((i, j))\n",
    "            que = tmp\n",
    "            \n",
    "        return matrix\n",
    "\n",
    "#     def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "#         ra = len(matrix)\n",
    "#         co = len(matrix[0])\n",
    "#         for i in range(ra):\n",
    "#             for j in range(co):\n",
    "#                 matrix[i][j] = min(matrix[i-1][j]+1 if i else 10001, matrix[i][j-1]+1 if j else 10001) if matrix[i][j] else 0\n",
    "\n",
    "#         for i in range(ra-1,-1,-1):\n",
    "#             for j in range(co-1,-1,-1):\n",
    "#                 matrix[i][j] = min(matrix[i+1][j]+1 if i<ra-1 else 10001, matrix[i][j+1]+1 if j<co-1 else 10001,matrix[i][j]) if matrix[i][j] else 0\n",
    "#         return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                l,t= 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = matrix[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = matrix[i][j - 1]\n",
    "                    \n",
    "                    matrix[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(matrix) - 1, -1 ,-1):\n",
    "            for j in range(len(matrix[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if matrix[i][j] != 0:\n",
    "                    if i < len(matrix) - 1:\n",
    "                        b = matrix[i + 1][j]\n",
    "\n",
    "                    if j < len(matrix[0]) - 1:\n",
    "                        r = matrix[i][j + 1]\n",
    "\n",
    "                    matrix[i][j] = min(matrix[i][j], min(r,b) + 1)\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        if not matrix:\n",
    "            return []\n",
    "        \n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if matrix[i][j]:\n",
    "                    matrix[i][j] = rows + cols\n",
    "                if i > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1) #up\n",
    "                if j > 0:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1) #left\n",
    "        \n",
    "        for i in range(rows-1, -1, -1):\n",
    "            for j in range(cols-1, -1, -1):\n",
    "                if i < rows - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1) #down\n",
    "                if j < cols - 1:\n",
    "                    matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1) #right\n",
    "        \n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix):\n",
    "        if not matrix:\n",
    "            return []\n",
    "        Maxlength = len(matrix) + len(matrix[0]) - 2\n",
    "        count = 0\n",
    "        \"\"\"0的四周的值赋值1（只要它不是0），\n",
    "        1的四周赋值2（只要它不是1，0）\n",
    "        假设一个n*n矩阵,距离上限为长+宽-2\"\"\"\n",
    "        def fun(i,j,n):\n",
    "            \"\"\"i,j:行和列\n",
    "            n:当前值\n",
    "            这个函数会将matrix[i][j]四周的值+1\"\"\"\n",
    "            count = 0\n",
    "            if i-1 >= 0 and matrix[i-1][j] > n+1:\n",
    "                matrix[i-1][j] = n+1\n",
    "                count += 1\n",
    "            if i+1 < len(matrix) and matrix[i+1][j] > n+1:\n",
    "                matrix[i+1][j] = n+1\n",
    "                count += 1\n",
    "            if j-1 >= 0 and matrix[i][j-1] > n+1:\n",
    "                matrix[i][j-1] = n+1\n",
    "                count += 1\n",
    "            if j+1 < len((matrix[0])) and matrix[i][j+1] > n+1:\n",
    "                matrix[i][j+1] = n+1\n",
    "                count += 1\n",
    "            return count\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] != 0:\n",
    "                    matrix[i][j] = Maxlength + 1\n",
    "                    count += 1\n",
    "        for n in range(Maxlength):\n",
    "            for i in range(len(matrix)):\n",
    "                for j in range(len(matrix[0])):\n",
    "\n",
    "                    if matrix[i][j] == n:\n",
    "                        count -= fun(i, j, n)\n",
    "                    if count == 0:\n",
    "                        return matrix\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        max_dis = m*n\n",
    "        # dp = [[max_dis if mat[i][j] != 0 else 0 for j in range(n)] for i in range(m)]\n",
    "        dp = mat\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] != 0:\n",
    "                    dp[i][j] = max_dis\n",
    "        # 从 i, j 向左上方寻找 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                if i > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j]+1)\n",
    "                if j > 0:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j-1]+1)\n",
    "        \n",
    "        # 从 i, j 向右下方寻找 0\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if dp[i][j] == 0:\n",
    "                    continue\n",
    "                if i < m-1:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i+1][j]+1)\n",
    "                if j < n-1:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][j+1]+1)\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    mat[i][j] = 9999999\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  mat[i][j-1] + 1\n",
    "        for i in range(m):\n",
    "            for j in range(n-2,0,-1):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i][j+1] + 1, mat[i][j])\n",
    "            else:\n",
    "                if mat[i][0] != 0 and n > 1:\n",
    "                    mat[i][0] =  mat[i][1] + 1\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i-1][j] + 1, mat[i][j])\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(m-2,-1,-1):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] =  min(mat[i+1][j] + 1, mat[i][j])\n",
    "\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        MAX = 1e6\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                \n",
    "                if mat[i][j] == 1:\n",
    "                    mat[i][j] = MAX\n",
    "\n",
    "                if i > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i - 1][j] + 1)\n",
    "                if j > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j - 1] + 1)\n",
    "        \n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                \n",
    "                if i < m - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i + 1][j] + 1)\n",
    "                if j < n - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j + 1] + 1)\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        coj = len(mat[0])\n",
    "        for i in range(row):\n",
    "            for j in range(coj):\n",
    "                if mat[i][j] != 0:\n",
    "                    mat[i][j] = 10000000\n",
    "                    if i - 1 >= 0:\n",
    "                        mat[i][j] = min(mat[i - 1][j] + 1, mat[i][j])\n",
    "                    if j - 1 >= 0:\n",
    "                        mat[i][j] = min(1 + mat[i][j - 1], mat[i][j])\n",
    "        for i in range(row)[::-1]:\n",
    "            for j in range(coj)[::-1]:\n",
    "                if mat[i][j] == 0:\n",
    "                    continue\n",
    "                if i + 1 < row:\n",
    "                    mat[i][j] = min(mat[i][j], 1 + mat[i + 1][j])\n",
    "                if j + 1 < coj:\n",
    "                    mat[i][j] = min(mat[i][j], 1 + mat[i][j + 1])\n",
    "        return mat\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] = float('inf') if mat[i][j] else 0\n",
    "        \n",
    "        # 左上角往下\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i - 1][j] + 1)\n",
    "                if j > 0:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j - 1] + 1)\n",
    "        \n",
    "        # 右下角往上\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i < m - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i + 1][j] + 1)\n",
    "                if j < n - 1:\n",
    "                    mat[i][j] = min(mat[i][j], mat[i][j + 1] + 1)\n",
    "\n",
    "        return mat\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append([i, j])\n",
    "                else:\n",
    "                    mat[i][j] = inf\n",
    "        d = [[0, 1],[0,-1],[1,0],[-1,0]]\n",
    "        t = 1\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                cur = queue.pop(0)\n",
    "                for i in range(4):\n",
    "                    nx, ny = cur[0] + d[i][0], cur[1] + d[i][1]\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n or mat[nx][ny] == 0 or t > mat[nx][ny]:\n",
    "                        continue\n",
    "                    mat[nx][ny] = t\n",
    "                    queue.append([nx, ny])\n",
    "            t += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # 多源BFS\n",
    "        # 找每个1到最近0的距离\n",
    "        def inArea(mat, r, c):\n",
    "            return r>=0 and r<len(mat) and c>=0 and c<len(mat[0])\n",
    "        \n",
    "        # 将所有0入队\n",
    "        # 直接在mat上记录结果，将所有1设为-1，表示没有被访问的结点和0点\n",
    "        q = []\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if mat[i][j] == 0:\n",
    "                    q.append([i, j])\n",
    "                else:\n",
    "                    mat[i][j] = -1\n",
    "        \n",
    "        adjs = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        while q!= []:\n",
    "            node = q.pop(0)\n",
    "            r, c = node\n",
    "            # mat[r][c] += 1\n",
    "            for adj in adjs:\n",
    "                r2 = r + adj[0]\n",
    "                c2 = c + adj[1]\n",
    "                if inArea(mat, r2, c2) and mat[r2][c2] == -1:\n",
    "                    mat[r2][c2] = mat[r][c] + 1\n",
    "                    q.append([r2, c2])\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        #copy\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                l,t= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i >0 :\n",
    "                        t= mat[i-1][j]\n",
    "                    if j >0:\n",
    "                        l = mat[i][j-1]\n",
    "                    mat[i][j] = min(l,t) + 1\n",
    "        \n",
    "        for i in range(len(mat)-1,-1,-1):\n",
    "            for j in range(len(mat[0])-1,-1,-1):\n",
    "                r,b= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i <len(mat)-1:\n",
    "                        b = mat[i+1][j]\n",
    "                    if j <len(mat[0])-1:\n",
    "                        r = mat[i][j+1]\n",
    "                    mat[i][j] = min(mat[i][j],min(r,b)+1)\n",
    "        return mat\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                l,t= 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i > 0:\n",
    "                        t = mat[i - 1][j]\n",
    "                    \n",
    "                    if j > 0:\n",
    "                        l = mat[i][j - 1]\n",
    "                    \n",
    "                    mat[i][j] = min(l,t) + 1\n",
    "        print(mat)\n",
    "        \n",
    "        for i in range(len(mat) - 1, -1 ,-1):\n",
    "            for j in range(len(mat[0]) - 1, -1, -1):\n",
    "                r,b = 10001,10001\n",
    "                if mat[i][j] != 0:\n",
    "                    if i < len(mat) - 1:\n",
    "                        b = mat[i + 1][j]\n",
    "\n",
    "                    if j < len(mat[0]) - 1:\n",
    "                        r = mat[i][j + 1]\n",
    "\n",
    "                    mat[i][j] = min(mat[i][j], min(r,b) + 1)\n",
    "        print(mat)\n",
    "        return mat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        每个0向四周扩散 进行BFS搜索\n",
    "        \"\"\"\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        queue = deque()\n",
    "        dirs = [(0,-1),(0,1),(1,0),(-1,0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                else:\n",
    "                    mat[i][j] = -1 #代表还未被访问\n",
    "        while queue:\n",
    "            x,y = queue.popleft()\n",
    "            for dx,dy in dirs:\n",
    "                new_x,new_y = x+dx,y+dy\n",
    "                if 0<=new_x<m and 0<=new_y<n and mat[new_x][new_y]==-1:\n",
    "                    mat[new_x][new_y] = mat[x][y]+1\n",
    "                    queue.append((new_x,new_y))\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        directions=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        queue=deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                else:\n",
    "                    mat[i][j]=-1\n",
    "\n",
    "        while queue:\n",
    "            x,y=queue.popleft()\n",
    "            for deltaX,deltaY in directions:\n",
    "                newX=x+deltaX\n",
    "                newY=y+deltaY\n",
    "                if 0<=newX<m and 0<=newY<n and mat[newX][newY]==-1:\n",
    "                    mat[newX][newY]=mat[x][y]+1\n",
    "                    queue.append((newX,newY))\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # 初始化动态规划的数组，所有的距离值都设置为一个很大的数\n",
    "        dist = [[10**9] * n for _ in range(m)]\n",
    "        # 如果 (i, j) 的元素为 0，那么距离为 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    dist[i][j] = 0\n",
    "        # 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序\n",
    "        for i in range(m):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i - 1 >= 0:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        # 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if i + 1 < m:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)\n",
    "                if j + 1 < n:\n",
    "                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        dp = [[float('inf')]*col for _ in range(row)]\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if mat[r][c] == 0:\n",
    "                    dp[r][c] = 0\n",
    "                else:\n",
    "                    up = dp[r-1][c] if r-1 >= 0 else float('inf')\n",
    "                    left = dp[r][c-1] if c-1 >= 0 else float('inf')\n",
    "                    dp[r][c] = min(up, left) + 1\n",
    "\n",
    "        \n",
    "        for r in range(row-1, -1, -1):\n",
    "            for c in range(col-1, -1, -1):\n",
    "                if mat[r][c] == 0:\n",
    "                    dp[r][c] = 0\n",
    "                else:\n",
    "                    down = dp[r+1][c] if r+1 < row else float('inf')\n",
    "                    right = dp[r][c+1] if c+1 < col else float('inf')\n",
    "                    dp[r][c] = min(min(down, right) + 1, dp[r][c])\n",
    "        \n",
    "        return dp\n",
    "                \n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        x_len = len(mat)\n",
    "        y_len = len(mat[0])\n",
    "        ans = [[None] * y_len for _ in range(x_len)]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for x in range(x_len):\n",
    "            for y in range(y_len):\n",
    "                if mat[x][y] == 0:\n",
    "                    ans[x][y] = 0\n",
    "                    queue.append((x,y))\n",
    "\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dif_x, dif_y in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                next_x, next_y = dif_x + x, dif_y + y\n",
    "                if 0<=next_x<x_len and 0<=next_y<y_len and ans[next_x][next_y] == None:\n",
    "                    ans[next_x][next_y] = ans[x][y] + 1\n",
    "                    queue.append((next_x, next_y))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        max_x = len(mat)\n",
    "        max_y = len(mat[0])\n",
    "\n",
    "        result = [[None for x in range(max_y)] for x in range(max_x)]\n",
    "\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(max_x):\n",
    "            for j in range(max_y):\n",
    "                if mat[i][j] == 0:\n",
    "                    result[i][j] = 0\n",
    "                    q.append([i, j])\n",
    "\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for x_bias, y_bias in  [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                new_x = i + x_bias\n",
    "                new_y = j + y_bias\n",
    "                if 0 <= new_x < max_x and 0 <= new_y < max_y and result[new_x][new_y] == None:\n",
    "                    result[new_x][new_y] = result[i][j] + 1\n",
    "                    q.append([new_x, new_y])\n",
    "\n",
    "        return result\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        每个0向四周扩散 进行BFS搜索\n",
    "        \"\"\"\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        seen = set()\n",
    "        queue = deque()\n",
    "        dirs = [(0,-1),(0,1),(1,0),(-1,0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    queue.append((i,j))\n",
    "                    seen.add((i,j))\n",
    "                    mat[i][j] = 2\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                x,y = queue.popleft()\n",
    "                for dx,dy in dirs:\n",
    "                    new_x,new_y = x+dx,y+dy\n",
    "                    if 0<=new_x<m and 0<=new_y<n and (new_x,new_y) not in seen:\n",
    "                        mat[new_x][new_y] = mat[x][y]+1\n",
    "                        queue.append((new_x,new_y))\n",
    "                        seen.add((new_x,new_y))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mat[i][j] -= 2\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        # def bfs(q, visited, step):\n",
    "        #     while q:\n",
    "        #         size = len(q)\n",
    "        #         for _ in range(size):\n",
    "        #             x, y = q.popleft()\n",
    "        #             for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):\n",
    "        #                 if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "        #                     continue\n",
    "        #                 if mat[nx][ny] == 0:\n",
    "        #                     return step\n",
    "        #                 if (nx, ny) not in visited:\n",
    "        #                     q.append((nx, ny))\n",
    "        #                     visited.add((nx, ny))       \n",
    "        #         step += 1\n",
    "\n",
    "        # m, n = len(mat), len(mat[0])\n",
    "        # ans = [[-1] * n for _ in range(m)]\n",
    "        \n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         ans[i][j] += 1\n",
    "        #         if mat[i][j] == 1:\n",
    "        #             q = deque()\n",
    "        #             visited = set()\n",
    "        #             q.append((i, j))\n",
    "        #             visited.add((i, j))\n",
    "                    \n",
    "        #             ans[i][j] = bfs(q, visited, 1)\n",
    "\n",
    "        # return ans\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        queue = deque()\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                    visited[i][j] = 1\n",
    "\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                x, y = queue.popleft()\n",
    "                if mat[x][y] == 1:\n",
    "                    res[x][y] = step\n",
    "                for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny] == 1:\n",
    "                        continue\n",
    "                    queue.append((nx, ny))\n",
    "                    visited[nx][ny] = 1\n",
    "            step += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "                    \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "        '''\n",
    "        求节点i到 最近 的0的距离\n",
    "        适合bfs\n",
    "        如果是从节点1出发，每个节点1都跑一遍bfs，时间复杂度是O(m^2*n^2)\n",
    "        横看成岭侧成峰\n",
    "        如果是从多个节点0一起出发，只跑一遍bfs，这就可以保证正确性了，这也叫多源bfs\n",
    "        建立一个超级源点？？\n",
    "        '''\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        q=[]\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                if not x:\n",
    "                    q.append((i,j))\n",
    "                    vis[i][j]=True\n",
    "        dist=0\n",
    "        while q:\n",
    "            dist+=1\n",
    "            tmp=[]\n",
    "            while q:\n",
    "                (x,y)=q.pop()\n",
    "                for i,j in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=i<m and 0<=j<n and not vis[i][j]:\n",
    "                        vis[i][j]=True\n",
    "                        tmp.append((i,j))\n",
    "                        ans[i][j]=dist\n",
    "            q=tmp\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        from collections import deque\n",
    "\n",
    "        nRow, nCol = len(mat), len(mat[0])\n",
    "\n",
    "        res = [[0 for _ in range(nCol)] for _ in range(nRow)]\n",
    "        visit = [[0 for _ in range(nCol)] for _ in range(nRow)]\n",
    "\n",
    "        queue = deque()\n",
    "\n",
    "        for r in range(len(mat)):\n",
    "            for c in range(len(mat[0])):\n",
    "                if mat[r][c] == 0:\n",
    "                    queue.append((r, c))\n",
    "                    visit[r][c] = 1\n",
    "                    \n",
    "        moves = [\n",
    "            [-1, 0],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [0, 1],\n",
    "        ]\n",
    "\n",
    "        step = 0\n",
    "        \n",
    "        while queue:\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                \n",
    "                x, y = queue.popleft()\n",
    "\n",
    "                if mat[x][y] == 1:\n",
    "                    res[x][y] = step\n",
    "\n",
    "                for move in moves:\n",
    "                    \n",
    "                    new_x, new_y = x + move[0], y + move[1]\n",
    "                    \n",
    "                    if 0 <= new_x < len(mat) and 0 <= new_y < len(mat[0]) and visit[new_x][new_y] == 0:\n",
    "                        \n",
    "                        queue.append((new_x, new_y))\n",
    "                        visit[new_x][new_y] = 1\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "  ### 多源最短路问题思路比较固定，大概分为以下几步： 1，设目标数组和标记数组，标记该点是否被访问到 2，寻找一开始的“源\",放入队列，并且标记已经访问过 2.当队列非空的时候，每次找队头元素，（记得弹出队列）四个方向（有时候是 八个方向）广搜，先判断是否超出边界或者被访问过，如果没有就把该点标记为访问过，按照题目要求要处理一下（这里是标记距离），然后放入队列即可\n",
    "class Solution:\n",
    "    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]\n",
    "        # 将所有的 0的下标 添加进初始队列中\n",
    "        q = collections.deque(zeroes_pos)\n",
    "        seen = set(zeroes_pos)\n",
    "\n",
    "        # 广度优先搜索\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:### 该点四个方向搜索\n",
    "                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen: ### 这些是没有处理过的1\n",
    "                    dist[ni][nj] = dist[i][j] + 1\n",
    "                    q.append((ni, nj)) ### 添加进来，准备在他周围继续搜索，\n",
    "                    ### 第一遍，所有的在0附近的1都搞完了\n",
    "                    ###继续pop，就会找到新的pop\n",
    "                    seen.add((ni, nj)) ### 已经处理过了\n",
    "        \n",
    "        return dist"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
